package queue_stack.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * // TODO 双栈解法再优化
 * @author yuisama
 * @date 2022/01/23 21:37
 **/
public class Num227_Calculate {
    // 存放整数的栈
    private Stack<Integer> s1 = new Stack<>();
    // 存放操作符的栈
    private Stack<Character> s2 = new Stack<>();
    // 存放操作符和优先级的映射,题目中只有加减乘除
    private Map<Character,Integer> map = new HashMap<>();
    public Num227_Calculate() {
        map.put('+',1);
        map.put('-',1);
        map.put('*',2);
        map.put('/',2);
    }
    public int calculate(String s) {
        // 先去除s中所有空格
        s = s.replaceAll(" ","");
        // 遍历s
        char[] cs = s.toCharArray();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (isNumber(c)) {
                // 碰到数字直接入栈
                int u = 0;
                int j = i;
                // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                while (j < n && isNumber(cs[j])) u = u * 10 + (cs[j++] - '0');
                s1.push(u);
                i = j - 1;
            }else {
                // 此时碰到运算符
                if (s2.isEmpty()) {
                    // 栈为空或者栈顶运算符优先级小于当前运算符，直接入栈
                    s2.push(c);
                }else {
                    char top = s2.peek();
                    if (map.get(c) > map.get(top)) {
                        s2.push(c);
                        continue;
                    }
                    while (!s2.isEmpty()) {
                        top = s2.peek();
                        // 栈顶运算符 >= 当前运算符
                        // 从s1中取出两个操作数
                        if (map.get(top) >= map.get(c)) {
                            int num1 = s1.pop();
                            int num2 = s1.pop();
                            int tmpRet = cal(num2,num1,top);
                            s2.pop();
                            // 将结果压入s1，将当前运算符压入s2
                            s1.push(tmpRet);
                        }else {
                            break;
                        }
                    }
                    s2.push(c);
                }
            }
        }
        // 再计算剩下的值
        while (!s2.isEmpty()) {
            int num1 = s1.pop();
            int num2 = s1.pop();
            char c = s2.pop();
            int ret = cal(num2,num1,c);
            s1.push(ret);
        }
        // 最终s1的栈顶就是计算后的值
        return s1.pop();
    }

    public int cal(int num1,int num2,char top) {
        int ret = 0;
        if (top == '+') {
            ret = num1 + num2;
        }else if (top == '-') {
            ret = num1 - num2;
        }else if (top == '*') {
            ret = num1 * num2;
        }else {
            ret = num1 / num2;
        }
        return ret;
    }

    public boolean isNumber(char c) {
        return Character.isDigit(c);
    }
}